from IPython.display import HTML df = lambda x: display(Image(filename=x)) uf = lambda x: display(Image(url=x)) do = HTML(''' reveal.''')

BLAST

Basic Local Alignment Search Tool

  • First iteration appeard ~1990
  • Number of iterations/versions
  • Extremely popular and well-used
  • NT, protein, etc. . . . blastp, blastn, blastx

How it works

  • split a sequence into kmers (word size) (11 for nt)
  • scan each sequence for that "word" . . . score along the way
  • also PSI-blast
In [25]:
from IPython.display import display, Image
display(Image(filename='kmers.png'))
do
Out[25]:
reveal.
In [27]:
df('blast-menu.png')
do
Out[27]:
reveal.
In [19]:
df = lambda x: display(Image(filename=x))
f = lambda x: display(Image(url=x))
In [ ]:
In [13]:
##Output

Output

Query  10141  TTCGAGAGTGAAGGAGTTCTGTAATTACCAACAAAAATACC--AAAGAGGCTATTGAAGT  10198
              ||||||||||||||||||||||||| ||||||||||| ||   ||||||||||||| |||
Sbjct  9304   TTCGAGAGTGAAGGAGTTCTGTAATCACCAACAAAAA-ACATTAAAGAGGCTATTGGAGT  9362

Query  10199  CAGGCCACTTGTGCCACGGCTTGAGCAAACCGTGC  10233
              |||||||||||||||||||||||||||||||||||
Sbjct  9363   CAGGCCACTTGTGCCACGGCTTGAGCAAACCGTGC  9397

But it's slow.

In [ ]:
Time Complexity
==============

O

As inputs approach bigger numbers, it's defined by its growth rate . . .

In [18]:
df('ncbi-dataset.png')
In [20]:
uf('https://nerdgerl.files.wordpress.com/2009/11/scale_plot1.jpg')

Blast is O(MN), where M=length of query sequence, N= size of database.

But speed is becoming more important. (high throughput & cheaper sequencing; clinical application) And things are just going to get worse.

In [ ]:
##Interlude: Lessons from SciPy
The same computational problem has often been solved in another field.b
In [ ]:
uf('http://www.nature.com/nbt/journal/v29/n11/images/nbt.2023-F2.gif')
In [ ]:
uf('http://s.hswstatic.com/gif/speech-recognition-5.jpg')
In [ ]:
uf('http://www.biopred.net/jpg/HMM-Fig1.jpg')
In [ ]:
Scientitsts often need "pipelines" . . .
In [ ]:
df('/media/VD_Research/Admin/PBS/Software/ngs_mapper-1.2.4/.ngs_mapper/docs/ngs_mapper/_images/ngs_mapper_diagram.pngb')
In [ ]:
uf('http://spiff.rit.edu/classes/phys373/lectures/cosmic_rays/raw_hst_image_big.gif')
In [ ]:
uf('http://heritage.stsci.edu/1999/16/images/raw814_600.jpg')
In [ ]:
uf('http://apod.nasa.gov/apod/image/1210/NGC2623_HLApugh.jpg')